// #include <iostream>
// using namespace std;
// #define int long long 
// const int N = 2020;
// long long C[N+1][N+1];
// int t, k;
// void initT2() {
//     for (int n = 0; n <= N; ++n) {
//         C[n][0] = C[n][n] = 1;
//         for (int j = 1; j < n; ++j)
//         {
//             C[n][j] = (C[n-1][j-1] + C[n-1][j]) % k;
//         }
           
//     }
// }
// // void initT1() {
// //     for (int n = 0; n <= N; ++n) {
// //         C[n][0] = C[n][n] = 1;
// //         for (int k = 1; k < n; ++k)
// //             C[n][k] = C[n-1][k-1] + C[n-1][k];
// //     }
// // }

// signed main() {

//     cin >> t >> k;
//     initT2();
//     for(int i = 0; i < t; i++) {
//         int n, m;
//         cin >> n >> m;
//         int count = 0;
//         for(int i = 0; i <= n; i++) {
//             for(int j = 0; j <= min(i, m); j++) {
//                 int temp = C[i][j];
//                 if(temp % k == 0) {
//                     count++;
//                 }
//             }
//         }
//         cout << count << endl;
//     }
//     return 0;
// }

#include<iostream>
#define int long long
#define inf 2e9
#define debug cout << "zlqwq"
#define llinf 1e18

using namespace std;
int t,k,n,m,f[2005][2005],ans[2005][2005];
signed main() {
	cin >> t >> k;
	for(int i = 0;i <= 2000;++i) {
		f[i][0] = 1;
	}
	for(int i = 1;i <= 2000;++i) {
		for(int j = 1;j <= 2000;++j) {
			f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % k;
			if(f[i][j] == 0 && i >= j) {
				ans[i][j]++;
			}
			ans[i][j] += ans[i][j - 1] + ans[i - 1][j] - ans[i - 1][j - 1];
		}
	}
	while(t--) {
		cin >> n >> m;
		cout << ans[n][m] << '\n';
	}
	return 0;
}

